package foundation.decomposed_prime_factor;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 求出区间[a,b]中所有整数的质因数分解。
 */
public class Main {
    static List<Integer> path = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        List<Integer> prime = getPrime(b);
        for (int i = a; i <= b; i++) {
            path.clear(); // 首先将上一步结果清除
            count(prime, i);
            System.out.print(i + "=");
            for (int j = 0; j < path.size(); j++) {
                System.out.print(path.get(j));
                if (j != path.size() - 1) {
                    System.out.print("*");
                } else {
                    System.out.println();
                }
            }
        }
    }

    /**
     * 利用回溯法求得数num的质因数分解字符串
     * @param list 所有质数
     * @param num
     * @return
     */
    public static boolean count(List<Integer> list, int num) {
        if (num == 1) {
            // 当num已经除到1了表示已经找到符合条件的所有质数
            return true;
        }
        // 单层逻辑递归
        for (int p : list) {
            if (num % p == 0) {
                path.add(p);
                boolean flag = count(list, num / p);
                if (flag) {
                    break;
                }
                // 到这里说明前面的路走不通，将之前的一步删除
                path.remove(path.size() - 1);
            }
        }
        return true;
    }

    /**
     * 求出 0 到 b 之间的所有素数
     * @param b
     * @return
     */
    public static List<Integer> getPrime(int b) {
        List<Integer> list = new ArrayList<>();
        // 质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。
        for (int i = 2; i < b; i++) {
            int j = 2;
            for (; j < (int)Math.sqrt(i) + 1; j++) {
                if (i != j && i % j == 0) {
                    break;
                }
            }
            if (j == (int)Math.sqrt(i) + 1) {
                list.add(i);
            }
        }
        return list;
    }
}
